package airthmetic.exercise.backtrack;

import java.util.*;

public class _51_N皇后 {
    public static List<List<String>> solveNQueens(int n) {
        // n 小于1 或者 大于一并且小于4时没有解
        if(n <1 || n>1 && n<4){
            return new ArrayList<List<String>>();
        }
        int level = 0;
        // 表示当前索引(行)那个列是皇后
        int[] nums = new int[n];
        Arrays.fill(nums,-1);
        // 表示列是否已被占用
        Set<Integer> lie = new HashSet();
        // 表示撇是否已被占用
        Set<Integer> pie = new HashSet();
        // 表示捺是否已被占用
        Set<Integer> na = new HashSet();
        List<List<String>> res = new ArrayList();
        backtrack(n,nums,level,lie,pie,na,res);
        return res;

    }

    public static void backtrack(int n, int[] nums, int level, Set<Integer> lie, Set<Integer> pie, Set<Integer> na, List<List<String>> res){
        // terminal
        if(level == n){
            // convert
            res.add(genResult(nums,n));
            return;
        }
        // process current logic
        for(int i=0; i< nums.length; i++){
            if(lie.contains(i)){
                continue;
            }
            // 行+列
            int levelPlusColumn = level + i;
            if(pie.contains(levelPlusColumn)){
                continue;
            }
            // 行-列
            int levelSubColumn = level - i;
            if(na.contains(levelSubColumn)){
                continue;
            }

            // 走到这里说明没有冲突
            nums[level] = i;
            lie.add(i);
            pie.add(levelPlusColumn);
            na.add(levelSubColumn);
            // drill down
            backtrack(n,nums,level+1,lie,pie,na,res);
            // backtrack
            nums[level] = -1;
            lie.remove(i);
            pie.remove(levelPlusColumn);
            na.remove(levelSubColumn);
        }

    }


    public static List<String> genResult(int[] queens,int n) {
        List<String> tempResult = new ArrayList();
        for (int i=0;i<queens.length;i++) {
            char[] row = new char[n];
            Arrays.fill(row,'.');
            row[queens[i]] = 'Q';
            tempResult.add(new String(row));
        }
        return tempResult;
    }

    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
    }
}
